#pragma once
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <time.h>

const static size_t FIXED_LENTH_NUM = 128 * 1024; // 申请128kb的大小

// 这是一个定长的内存池
// 这个内存池每次按照T类型的大小进行切分操作
template <class T>
class MemoryPool
{
public:
    MemoryPool() : _memory(nullptr), _remainsize(0), _freelist(nullptr)
    {
    }
    T *New()
    {
        T *obj = nullptr;
        // 如果释放空间的链表不为空，则优先使用被释放的空间
        if (_freelist)
        {
            // 链表的头删
            void *next = (*(void **)_freelist);
            obj = (T *)_freelist;
            _freelist = next;
        }
        else
        {
            if (_remainsize < sizeof(T))
            {
                _remainsize = FIXED_LENTH_NUM;
                _memory = (char *)malloc(FIXED_LENTH_NUM);
                if (_memory == nullptr)
                {
                    throw std::bad_alloc();
                }
            }

            obj = (T *)_memory; // 第一次切分时obj指向大块内存的起始位置

            // 这里存在一个问题，某些平台下指针的大小比int short等类型大
            // 如果我们使用T类型的大小对_memory指针进行++，就会导致后续删除的时候多删除一部分空间，导致内存空间的浪费
            // 因此我们需要做一些修改
            //  _memory += sizeof(T);  // 切分完毕_memory指针像后移动
            size_t Size = sizeof(T) < sizeof(void *) ? sizeof(void *) : sizeof(T);
            _memory += Size;
            // 此时存在这样一个问题：
            // 最后一次切分后，_memory有可能会发生越界访问越界访问
            // 此时我们需要在类内部定义一个新的对象，这个对象用来表示内存块剩余空间的大小
            _remainsize -= Size;
        }
        // 定位new，显示调用T的构造函数进行初始化
        new (obj) T;

        return obj;
    }

    void Delete(T *obj)
    {
        // 显示调用T的析构函数
        obj->~T();
        // 这里用链表管理被释放的空间
        // 采用头插的方式
        void *next = _freelist;
        // 让obj的头部空间保存下一个节点的地址
        // 因为分为64位机器和32位机器，导致指针的大小不一样
        // 为了让代码在各个平台下都能运行，这里采用二级指针来解决这个问腿
        *(void **)obj = next;
        _freelist = obj;
    }

    ~MemoryPool()
    {
        free(_memory);
        _memory = nullptr;
    }

private:
    char *_memory;      // 大块内存
    size_t _remainsize; // 内存块剩余空间大小
    void *_freelist;    // 管理被释放的内存的链表
};

struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;

	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

void TestObjectPool()
{
    // 申请释放的轮次
    const size_t Rounds = 5;

    // 每轮申请释放多少次
    const size_t N = 100000;

    std::vector<TreeNode *> v1;
    v1.reserve(N);

    size_t begin1 = clock();
    for (size_t j = 0; j < Rounds; ++j)
    {
        for (int i = 0; i < N; ++i)
        {
            v1.push_back(new TreeNode);
        }
        for (int i = 0; i < N; ++i)
        {
            delete v1[i];
        }
        v1.clear();
    }

    size_t end1 = clock();

    std::vector<TreeNode *> v2;
    v2.reserve(N);

    MemoryPool<TreeNode> TNPool;
    size_t begin2 = clock();
    for (size_t j = 0; j < Rounds; ++j)
    {
        for (int i = 0; i < N; ++i)
        {
            v2.push_back(TNPool.New());
        }
        for (int i = 0; i < N; ++i)
        {
            TNPool.Delete(v2[i]);
        }
        v2.clear();
    }
    size_t end2 = clock();

    std::cout << "new cost time:" << end1 - begin1 << std::endl;
    std::cout << "object pool cost time:" << end2 - begin2 << std::endl;
}